// 这个字典的主要功能就两个
// 1. 存放单词  2. 查找单词是否存在
// next: 保存着下一个字符 i 的节点引用
// isEnd: 当前节点是否可以作为一个单词的结束位置

var Trie = function () {
  this.root = new TrieNode();
};

function TrieNode() {
  this.next = new Map();
  this.isEnd = false;
}

Trie.prototype.insert = function (word) {
  if (!word) return;
  var node = this.root;
  for (let i = 0; i < word.length; i++) {
    if (!node.next.has(word[i])) {
      node.next.set(word[i], new TrieNode());
    }
    node = node.next.get(word[i]);
  }
  node.isEnd = true;
};

Trie.prototype.search = function (word) {
  if (!word) return false;
  var node = this.root;
  for (let i = 0; i < word.length; i++) {
    if (!node.next.has(word[i])) {
      return false;
    }
    node = node.next.get(word[i]);
  }
  return node.isEnd;
};

Trie.prototype.startsWith = function (prefix) {
  if (!prefix) return true;
  var node = this.root;
  for (let i = 0; i < prefix.length; i++) {
    if (!node.next.has(prefix[i])) {
      return false;
    }
    node = node.next.get(prefix[i]);
  }
  return true;
};
